package tasks.leetcode.爬楼梯;

/**
 * 爬楼梯问题.md
 * https://leetcode.cn/problems/climbing-stairs/description/
 */
public class Task70_1 {

    public static void main(String[] args) {
        int i = new Task70_1().climbStairs(10);
        System.out.println(i);
    }

    /**
     * 使用递归的方法，可以解决问题，但是效率太低了，提高直接超时了；
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        int nemo[] = new int[n+1];
        return getNemoClimbStairs(nemo, n);
    }

    private int getNemoClimbStairs(int[] nemo, int n) {
        if (nemo[n] > 0) {
            return nemo[n];
        }
        if (n == 1) {
            nemo[n] = 1;
        } else if (n == 2) {
            nemo[n] = 2;
        } else {
            nemo[n] = getNemoClimbStairs(nemo, n - 1) + getNemoClimbStairs(nemo, n - 2);
        }
        return nemo[n];
    }
}
